package com.cheng.learn.leetcode;

import java.util.Arrays;

/**
 * @description: 零钱兑换题
 * @author: ChengHaiZhu
 * @create: 2021-03-21 20:05
 **/
public class CoinChange322 {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int n = coins.length - 1;
        int count = 0;
        while(n >= 0){
            count += amount / coins[n];
            if(coins[n] == 1 || amount % coins[n] == 0){
                return count;
            }
            amount = amount % coins[n];
            n --;
        }
        return -1;
    }
}
